package q216_combinationSum3;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> bin = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k > n){
            return res;
        }
        dfs(k, n, 0, 1);
        return res;
    }

    private void dfs(int k, int n, int temp, int cur) {
//        if (temp > n || bin.size() > k) {
//            return;
//        }
//
//        if (temp == n && bin.size() == k) {
//            res.add(new ArrayList<>(bin));
//            return;
//        }
        // 更加简约的写法
        if (temp > n) {
            return;
        }

        if (bin.size() == k) {
            if (temp == n) {
                res.add(new ArrayList<>(bin));
            }
            return;
        }

        for (int i = cur; i <= 9; i++) {
            bin.add(i);
            temp += i;
            dfs(k, n, temp, i + 1);
            bin.remove(bin.size() - 1);
            temp -= i;
        }
    }
}
